#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
class Solution
{
private:
    class tire_node
    {
    public:
        tire_node(const char ch = '\0') : c(ch) { memset(sons, 0, sizeof sons); }
        tire_node *get_son(char ch)
        {
            return sons[ch - 'a'];
        }
        tire_node *add_son(char ch)
        {
            return sons[ch - 'a'] = new tire_node(ch);
        }
        bool check_end()
        {
            return end != 0;
        }
        bool check_son()
        {
            for (int i = 'a'; i <= 'z'; i++)
            {
                if (get_son(i))
                    return true;
            }
            return false;
        }
        bool add_end()
        {
            end++;
            return true;
        }
        bool del_end()
        {
            end--;
            return true;
        }

    private:
        char c;
        size_t end = 0;
        tire_node *sons[26];

    public:
        class tire_tree
        {
        public:
            bool insert(const string &str, int &res)
            {
                tire_node *cur = root;
                for (int i = 0; i < str.size(); i++)
                {
                    tire_node *son = cur->get_son(str[i]);
                    if (!son)
                        son = cur->add_son(str[i]);
                    cur = son;
                    if (cur->check_end() && i < str.size() - 1)
                    {
                        cur->del_end();
                        res -= i + 2;
                    }
                }
                if (cur->check_end() || cur->check_son())
                    return false;
                cur->add_end();
                return true;
            }

        private:
            tire_node *root = new tire_node();
        };
    };

public:
    int minimumLengthEncoding(vector<string> &words)
    {
        int res = 0;
        tire_node::tire_tree tire;
        for (auto &word : words)
        {
            reverse(word.begin(), word.end());
            if (tire.insert(word, res))
                res += word.size() + 1;
        }
        return res;
    }
};